package com.hch.algorithm.leet;

import com.hch.algorithm.binarytree.ThreeNode;
import com.hch.algorithm.binarytree.TreeNode;

import java.util.List;

/**
 * @author heconghui
 */
public interface BinaryTreeLeetBook {
    /**
     * //    力扣654 题给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
     *     //
     *     //二叉树的根是数组 nums 中的最大元素。
     *     //左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
     *     //右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
     *     //返回有给定数组 nums 构建的 最大二叉树 。
     * @param nums
     * @return
     */
    TreeNode constructMaximumBinaryTree(int[] nums);

    /**
     *  力扣105 题 根据前中序遍历得到当前二叉树
     * @param preorder
     * @param inorder
     * @return
     */
    TreeNode<Integer> buildTree105(int[] preorder, int[] inorder);

    /**
     *  力扣 106
     * @param postorder 后序数组
     * @param inorder 前序数组
     * @return 原生二叉树
     */
    TreeNode<Integer> buildTree106(int[] postorder, int[] inorder);

    //    力扣第 116 题

    /**
     *
     * @param root
     * @return
     */

    ThreeNode connect(ThreeNode root);

    /**
     * //力扣114 题 将二叉树展开为链表
     * @param root
     */
    void flatten(TreeNode root);

    /**
     * 力扣652 寻找重复子树
     * @param root  二叉树
     * @return
     *
     */
    List<TreeNode> findDuplicateSubtrees(TreeNode root);

    /**
     * @param root
     * @param k
     * @return
     */
    int kthSmallest(TreeNode<Integer> root, int k);

    /**
     * //538 题 BST 转化累加树
     * @param root
     * @return
     */
    TreeNode convertBST(TreeNode<Integer> root);

    /**
     * //538 题 BST 转化累加树
     * @param root
     * @param key
     * @return
     */
    TreeNode deleteNode(TreeNode<Integer> root, int key);

}

